Matrix geometric method
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
top
In probability theory, the matrix geometric method is a method for the analysis of quasi-birth–death processes, continuous-time Markov chain whose transition rate matrices with a repetitive block structure.cite-ref-1[1] The method was developed "largely by Marcel F. Neuts and his students starting around 1975."cite-ref-2[2]
Contents
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Method description
The method requires a transition rate matrix with tridiagonal block structure as follows
Q = ( B 00 B 01 B 10 A 1 A 2 A 0 A 1 A 2 A 0 A 1 A 2 A 0 A 1 A 2 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ) {\displaystyle Q={\begin{pmatrix}B_{00}&B_{01}\\B_{10}&A_{1}&A_{2}\\&A_{0}&A_{1}&A_{2}\\&&A_{0}&A_{1}&A_{2}\\&&&A_{0}&A_{1}&A_{2}\\&&&&\ddots &\ddots &\ddots \end{pmatrix}}}
where each of B00, B01, B10, A0, A1 and A2 are matrices. To compute the stationary distribution π writing π Q = 0 the balance equations are considered for sub-vectors πi
π π 0 B 00 + π π 1 B 10 = 0 π π 0 B 01 + π π 1 A 1 + π π 2 A 0 = 0 π π 1 A 2 + π π 2 A 1 + π π 3 A 0 = 0 ⋮ ⋮ π π i − − 1 A 2 + π π i A 1 + π π i + 1 A 0 = 0 ⋮ ⋮ {\displaystyle {\begin{aligned}\pi _{0}B_{00}+\pi _{1}B_{10}&=0\\\pi _{0}B_{01}+\pi _{1}A_{1}+\pi _{2}A_{0}&=0\\\pi _{1}A_{2}+\pi _{2}A_{1}+\pi _{3}A_{0}&=0\\&\vdots \\\pi _{i-1}A_{2}+\pi _{i}A_{1}+\pi _{i+1}A_{0}&=0\\&\vdots \\\end{aligned}}}
Observe that the relationship
π π i = π π 1 R i − − 1 {\displaystyle \pi _{i}=\pi _{1}R^{i-1}}
holds where R is the Neut's rate matrix,cite-ref-3[3] which can be computed numerically. Using this we write
( π π 0 π π 1 ) ( B 00 B 01 B 10 A 1 + R A 0 ) = ( 0 0 ) {\displaystyle {\begin{aligned}{\begin{pmatrix}\pi _{0}&\pi _{1}\end{pmatrix}}{\begin{pmatrix}B_{00}&B_{01}\\B_{10}&A_{1}+RA_{0}\end{pmatrix}}={\begin{pmatrix}0&0\end{pmatrix}}\end{aligned}}}
which can be solve to find π0 and π1 and therefore iteratively all the πi.
Computation of R
The matrix R can be computed using cyclic reductioncite-ref-4[4] or logarithmic reduction.cite-ref-5[5]cite-ref-6[6]
Matrix analytic method
External links
• Performance Modelling and Markov Chains (part 2) by William J. Stewart at 7th International School on Formal Methods for the Design of Computer, Communication and Software Systems: Performance Evaluation
References
cite-note-11. ↑ citerefharrisonpatel1992Harrison, Peter G.; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley. pp. 317–322. ISBN 0-201-54419-9.
cite-note-66. ↑ citerefp-rezvan-houdt2011Pérez, J. F.; Van Houdt, B. (2011). "Quasi-birth-and-death processes with restricted transitions and its applications" (PDF). Performance Evaluation. 68 (2): 126. doi:10.1016/j.peva.2010.04.003. hdl:10067/859850151162165141.
cite-note-88. ↑ citerefbolchgreinerde-meertrivedi2006Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Trivedi, Kishor Shridharbhai (2006). Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications (2 ed.). John Wiley & Sons, Inc. p. 259. ISBN 0471565253.